package algorithm.easy;

import pojo.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: LeafSimilar872
 * @description: 872. 叶子相似的树
 * @date 2021/5/1011:21
 * @since V1.0
 */
public class LeafSimilar872 {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> fun = fun(root1);
        List<Integer> fun2 = fun(root2);
        if (fun.size()!=fun2.size()) return false;
        for (int i=0;i<fun.size();i++){
            if (!fun.get(i).equals( fun2.get(i))) return false;
        }
        return true;
    }

    public List<Integer> fun(TreeNode root){
        TreeNode t = root;
        Deque<TreeNode> stack = new LinkedList<>();
        ArrayList<Integer> arr = new ArrayList<>();
        //中序遍历
        while (t!=null || !stack.isEmpty()){
            if (t!=null){
                stack.push(t);
                t = t.left;
            }else {
                TreeNode pop = stack.pop();
                //加入集合
                if (pop.left==null && pop.right==null){
                    arr.add(pop.val);
                }
                t = pop.right;
            }
        }
        return arr;
    }
}
